In this paper, we revisit the classic problem of run generation. Rungeneration is the first phase of external-memory sorting, where the objectiveis to scan through the data, reorder elements using a small buffer of size M ,and output runs (contiguously sorted chunks of elements) that are as long aspossible. We develop algorithms for minimizing the total number of runs (orequivalently, maximizing the average run length) when the runs are allowed tobe sorted or reverse sorted. We study the problem in the online setting, bothwith and without resource augmentation, and in the offline setting. (1) We analyze alternating-up-down replacement selection (runs alternatebetween sorted and reverse sorted), which was studied by Knuth as far back as1963. We show that this simple policy is asymptotically optimal. Specifically,we show that alternating-up-down replacement selection is 2-competitive and nodeterministic online algorithm can perform better. (2) We give online algorithms having smaller competitive ratios with resourceaugmentation. Specifically, we exhibit a deterministic algorithm that, whengiven a buffer of size 4M , is able to match or beat any optimal algorithmhaving a buffer of size M . Furthermore, we present a randomized onlinealgorithm which is 7/4-competitive when given a buffer twice that of theoptimal. (3) We demonstrate that performance can also be improved with a small amountof foresight. We give an algorithm, which is 3/2-competitive, withforeknowledge of the next 3M elements of the input stream. For the extreme casewhere all future elements are known, we design a PTAS for computing the optimalstrategy a run generation algorithm must follow. (4) Finally, we present algorithms tailored for nearly sorted inputs whichare guaranteed to have optimal solutions with sufficiently long runs.
展开▼
